package com.lw.leetcode.other.b;

/**
 * Created with IntelliJ IDEA.
 * 866. 回文素数
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/7 15:40
 */
public class PrimePalindrome {

    public static void main(String[] args) {
        PrimePalindrome test = new PrimePalindrome();

        // 101
//        int n = 13;

        // 100030001
        int n = 9999999;

        // 100030001
//        int n = 99999999;

        int i = test.primePalindrome(n);
        System.out.println(i);
    }

    private int item;
    private int flag;
    private int max;

    public int primePalindrome(int n) {
        int[] arr = {2, 3, 5, 7, 11, 101};
        for (int i : arr) {
            if (n <= i) {
                return i;
            }
        }
        int t = n;
        int c = 0;
        while (t > 0) {
            t /= 10;
            c++;
        }
        flag = c & 1;
        c >>= 1;
        item = n;
        max = flag == 1 ? 9 : 0;
        while (c > 0) {
            c--;
            item /= 10;
            max = max * 10 + 9;
        }
        item--;
        long next = next();
        while (next < n || !find(next)) {
            next = next();
        }
        return (int) next;
    }

    private boolean find(long t) {
        if ((t & 1) == 0) {
            return false;
        }
        int v = (int) Math.pow(t, 0.5);
        int i = 3;
        while (i <= v) {
            if (t % i == 0) {
                return false;
            }
            i++;
        }
        return true;
    }

    private long next() {
        if (item == max) {
            if (flag == 1) {
                flag = 0;
                item = (max + 1) / 10;
            } else {
                flag = 1;
                item = max + 1;
                max = max * 10 + 9;
            }
        } else {
            item++;
        }
        long v = item;
        int t = item;
        if (flag == 1) {
            t /= 10;
        }
        while (t > 0) {
            v = v * 10 + t % 10;
            t /= 10;
        }
        return v;
    }

}
